//
// Description: 528. 按权重随机选择
// Created by Loading on 2021/8/30.
//

#include <bits/stdc++.h>

using namespace std;

class Solution {
private:
    // 前缀和数组
    vector<int> prefix_Sum;
public:
    explicit Solution(vector<int> &w) {
        /* 求前缀和方法 */
        partial_sum(w.begin(), w.end(), back_inserter(prefix_Sum));
    }

    int pickIndex() {
        int random = rand() % prefix_Sum.back();
        return upper_bound(prefix_Sum.begin(), prefix_Sum.end(), random) - prefix_Sum.begin();
    }
};

int main() {
    vector<int> w = {1, 3};
    auto *obj = new Solution(w);
    int p1 = obj->pickIndex();
    int p2 = obj->pickIndex();
    int p3 = obj->pickIndex();
    int p4 = obj->pickIndex();
    cout << p1 << " " << p2 << " " << p3 << " " << p4 << endl;

    return 0;
}